This disclosure relates generally to hierarchical circuit layout optimization, and more specifically to obtaining a feasible integer solution in a hierarchical circuit layout optimization.
Layout optimization is a powerful technique for design migration, circuit performance tuning and design for manufacturing. For example, with layout optimization, a symbolic layout can be compacted to minimize the total area of a circuit design, a crude layout can be legalized to meet a set of design ground rules, a layout can be migrated from one technology to another, critical nets can be spaced farther apart to reduce coupling noise, device sizes can be changed to improve circuit performance, wires of a layout can be spread apart to make use of white space to improve the random defect yield, and critical features can be modified to remove lithography hot spots.
In modern very large scale integration (VLSI) designs, layout optimization is becoming more important as layouts and design ground rules become more complicated. For layout optimization of a typical VLSI design, not only geometric objects in the layouts must pass design ground rule checking in terms of spacing, width, etc., but also locations of the objects must be integer due to a requirement imposed by the structures of industrial layout databases and manufacturing considerations. In older technologies, directly rounding the real value obtained by layout optimization tools to the nearest manufacturing grid may be sufficient to meet design rule constraints. However, in modern deep sub-micron technologies where the manufacturing grid can be as small as 1 nanometer (nm) and the design rule value can be very close to the grid value, such trivial rounding may not work well and lead to design rule violation. Therefore, the integer requirement on the locations of the geometric objects has become more critical in modern VLSI circuit layout optimization.
One type of circuit layout optimization technique that has applicability to hierarchical layouts is a flat layout optimization. Flat layout optimization techniques are generally formulated as a special form of linear programming, which includes only two-variable difference constraints. To take advantage of this property, a graph-based algorithm is used to speed up the computation. However, flat layout optimization techniques have limits in applications. In particular, flat layout optimization techniques are unable to handle layout hierarchy and have difficulty handling a large problem size. Thus, the typical layouts that these flat layout optimization techniques can operate on are shapes in library cells, shapes in small flat macros, and wires residing at one level of design hierarchy of a large layout.
As a result, flat layout optimization techniques do not work very well for a VLSI chip design such as a microprocessor that is organized hierarchically with many levels of design hierarchy with different orientations. The hierarchical representation of a VLSI layout not only carries designers' intent, but also makes design checking and verification easier. If a hierarchical design is flattened in order to apply flat layout optimization techniques, the designers' intent such as repetitions, mirroring and rotations of cells will be lost. Moreover, the flattening will cause the problem size to increase dramatically. For example, given a layout consisting of n instances of a cell A, then it is assumed that there are v variables to be optimized in the cell A. Then, there will be n*v variables to represent the shapes in the flattened layout, while the hierarchical layout can be modeled by using only n+v variables. On the other hand, if flat layout optimization techniques are used with a hierarchical design in a bottom-up or top-down fashion, i.e., applying the flat approaches on part of the design based on the design hierarchy, then the global view for optimization may be lost and it may lead to a sub-optimal solution or even fail to find a feasible solution.
As a result, it has become necessary to develop hierarchical layout optimization techniques. Generally, the hierarchical layout optimization problem is formulated as a linear programming problem; however, as noted above, the principal requirement in layout modification is that the resultant shape edge and cell locations must be integer. The integer requirement of the layout locations gives rise to integer programming problems when attempting to use optimization techniques on the hierarchical layouts. Previous hierarchical layout optimization techniques have focused on the hierarchical layout compaction problems that are solved as an integer linear programming problem (ILP) using general purpose ILP solvers. These approaches suffer run-time problems with large designs.
It is well-known that ILP is an NP-hard problem. Another drawback is that a general purpose ILP solver has a difficult time handling conflicting input constraints and will often fail to return a solution. Various attempts have been made to overcome these problems, but these approaches suffer from additional problems caused by integer constraints such as failing to meet abutment/alignment constraints. Failing to meet abutment/alignment constraints result in pull-apart and/or misalignment of complicated VLSI designs. A pull-apart causes an open circuit. A misalignment causes a design rule violation. Both of them have to be avoided in a hierarchical layout optimization.
Therefore, it is desirable to develop a technique that can solve the large hierarchical layout optimization problem by optimizing both cell locations and shape edge locations at the same time, while preventing pull-apart and misalignment.